/**
 * Created by loso on 2017/3/27.
 */
public class _204_CountPrimes {
    public static int countPrimes(int n) {
        //求质数 个数
        if (n <= 1) {
            return 0;
        }

        int result = 0;
        boolean[] arr = new boolean[n];
        for (int i = 2; i < n; i++) {

            //如果arr[i]是质数则将其倍数全部标记为合数，否则不予考虑
            if (!arr[i]) {
                result++;
            } else {
                continue;
            }

            int j = 2;
            while (i * j < n) {
                arr[i * j] = true;
                j++;
            }
        }

        return result;
    }


}
